#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <iostream>

template <typename TYPE>
class Node
{
public:
	Node(TYPE data, Node *next=0) : data(data), next(next) {}
	TYPE data;
	Node<TYPE> *next;
};

class LinkedListIteratorException
{
    friend std::ostream &operator <<(std::ostream &os, const LinkedListIteratorException &e)
    {
        os << e.message.c_str();
        return os;
    }
public:
	LinkedListIteratorException(const std::string &message) : message(message) {}
private:
	std::string message;
};

template <typename TYPE>
class LinkedListIterator
{
   friend std::ostream &operator <<(std::ostream &os, const LinkedListIterator<TYPE> &it)
   {
      os << it.current;
      return os;
   }

public:
	LinkedListIterator(Node<TYPE> *current) :
      current(current)
   {
   }

	TYPE &operator *()
   {
      if (current == NULL)
      {
         throw LinkedListIteratorException("Cannot dereference iterator. List is empty or iterator points beyond the end");
      }
      return current->data;
   }

	LinkedListIterator<TYPE> operator ++()
   {
      if (current == NULL)
      {
         throw LinkedListIteratorException("Cannot increment iterator. List is empty or iterator points beyond the end");
      }
      current = current->next;
      return *this;
   }
   
	bool operator ==(const LinkedListIterator<TYPE> &other) {return current == other.current;} 
	bool operator !=(const LinkedListIterator<TYPE> &other) {return !(*this == other);}
private:
	Node<TYPE> *current;
};

template <typename TYPE>
class LinkedList
{
	friend std::ostream &operator <<(std::ostream &os, const LinkedList<TYPE> &linkedList)
   {
      Node<TYPE> *p = linkedList.head;
      while (p) {
         os << p->data << " ";
         p = p->next;
      }
      return os;
   }
public:
   LinkedList() : head(NULL)
   {
   }

   ~LinkedList()
   {
      clear();
   }

	void insert(TYPE value)
   {
      Node<TYPE> *p = new Node<TYPE>(value, head);
      head = p;
   }
   
   void clear()
   {
      Node<TYPE> *to_delete;
      Node<TYPE> *p = head;
      while (p)
      {
         to_delete = p;
         p = p->next;
         delete to_delete;
      }
      head = NULL;
   }

	LinkedListIterator<TYPE> begin()
   {
      return LinkedListIterator<TYPE>(head);
   }
	
   LinkedListIterator<TYPE> end() 
   {
      return LinkedListIterator<TYPE>(0);
   }
private:
	Node<TYPE> *head;
};

#endif
